package 字符串.数据压缩.LZW算法压缩;

import 字符串.单词查找树.三向单词查找树的符号表;
import algs4.BinaryStdIn;
import algs4.BinaryStdOut;

/**
 * @description:
 * @author: ywk
 * @date: 2021-09-20
 */
public class LZW {
    public static void main(String[] args) {
        compress("ABRACADABRABRABRA");
    }

    private static final int R = 256;
    private static final int L = 4096;
    private static final int W = 12;

    public static void compress(String input) {
//        String input = BinaryStdIn.readString();
        三向单词查找树的符号表.TST<Integer> st = new 三向单词查找树的符号表.TST<>();
        for (int i = 0; i < R; i++) {
            st.put("" + (char) i, i);
        }
        int code = R + 1;
        while (input.length() > 0) {
            String s = st.longestPrefixOf(input);
            BinaryStdOut.write(st.get(s), W);
            int t = s.length();
            if (t < input.length() && code < L) {
                st.put(input.substring(0, t + 1), code++);
            }
            input = input.substring(t);
        }
        BinaryStdOut.write(R, W);
        BinaryStdOut.close();
    }

    public static void expand() {
        String[] st = new String[L];
        int i;
        for (i = 0; i < R; i++) {
            st[i] = "" + (char) i;
        }
        st[i++] = " ";
        int codeword = BinaryStdIn.readInt(W);
        String val = st[codeword];
        while (true) {
            BinaryStdOut.write(val);
            codeword = BinaryStdIn.readChar(W);
            if (codeword == R) {
                break;
            }
            String s = st[codeword];
            if (i == codeword) {
                s = val + val.charAt(0);
            }
            if (i < L) {
                st[i++] = val + s.charAt(0);
            }
            val = s;
        }
        BinaryStdOut.close();
    }
}
